/*
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.rules;

import java.util.BitSet;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.onegravity.sudoku.solver.HintResource;
import com.onegravity.sudoku.solver.R;
import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.core.IndirectHint;
import com.onegravity.sudoku.solver.core.IndirectHintProducer;
import com.onegravity.sudoku.solver.data.Block;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.Column;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.data.Region;
import com.onegravity.sudoku.solver.data.Row;

/**
 * Sue de Coq producer
 * @author Emanuel Moecklin
 */
public class SueDeCoqProducer implements IndirectHintProducer {

	@Override
    public void getHints(Grid grid, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
        getHints(grid, Block.class, Column.class, accu);
        getHints(grid, Block.class, Row.class, accu);
    }
    
	private void getHints(Grid grid, Class<? extends Region> regionType1, Class<? extends Region> regionType2, HintsAccumulator accu)
						  throws StopHintProductionException, InterruptedException {

		// (1) find two intersecting regions
		for (Region region1 : grid.getRegions(regionType1)) {
			for (Region region2 : grid.getRegions(regionType2)) {
				if (Thread.interrupted()) throw new InterruptedException();
				if (!region1.crosses(region2)) continue;

				// (2) check whether the intersection has either:
				// - two cells with with 4 candidates or
				// - three cells with 5 candidates  
				List<Cell> intersection = region1.commonCells(region2);
				BitSet intersectionPotentials = new BitSet();
				int nrOfCells = getUnion(intersectionPotentials, intersection, null);
				if ((nrOfCells==2 && intersectionPotentials.cardinality()==4) || (nrOfCells==3 && intersectionPotentials.cardinality()==5)) {

					// (3) let's find bivalue cells in the relative complements of the two regions that match the intersection's candidates 
					List<Cell> region1Cells = region1.getCellSet();
					List<Cell> region2Cells = region2.getCellSet();
					// create relative complement of region 2 in region 1
					List<Cell> complementCells1 = region1.getCellSetClone();
					complementCells1.removeAll(region2Cells);
					// create relative complement of region 1 in region 2
					List<Cell> complementCells2 = region2.getCellSetClone();
					complementCells2.removeAll(region1Cells);
					// (3.1) let's find bivalue cells in the first region's compliment 
					for (Cell cell1:complementCells1) {
						if (!cell1.isEmpty()) continue; 
						BitSet potentials1 = (BitSet) cell1.getPotentialValues().clone();
						if (potentials1.cardinality()!=2) continue;
						potentials1.and(intersectionPotentials);
						if (potentials1.cardinality()!=2) continue;
						// (3.2) let's find bivalue cells in the second region's compliment (must have different canidates than the first bivalue cell) 
						for (Cell cell2:complementCells2) {
							if (!cell2.isEmpty()) continue; 
							BitSet potentials2 = (BitSet) cell2.getPotentialValues().clone();
							if (potentials2.cardinality()!=2 || potentials2.intersects(potentials1)) continue;
							potentials2.and(intersectionPotentials);
							if (potentials2.cardinality()!=2) continue;
							// we found a Sue de Coq, let's find out if there are removable potentials
							BitSet remainingPotentials = (BitSet) intersectionPotentials.clone();
							remainingPotentials.andNot(potentials2);
							Map<Cell, BitSet> removablePotentials = getRemovablePotentials(complementCells1, remainingPotentials, cell1);
							remainingPotentials.andNot(potentials1);
							remainingPotentials.or(potentials2);
							removablePotentials.putAll( getRemovablePotentials(complementCells2, remainingPotentials, cell2) );
							IndirectHint hint = new SueDeCoqHint(intersection, cell1, cell2, region1, region2, removablePotentials);
							if (hint != null && hint.isWorth()) accu.add(hint);
						}
					}
					
				}
				
			} // for (Region region2 : grid.getRegions(regionType2)) {
		} // for (Region region1 : grid.getRegions(regionType1)) {
	}

	/**
	 * Collects all candidates from empty cells (union)
	 * @param candidates The BitSet that will contain the union of all candidates
	 * @param cells The cells processed by this method
	 * @param excludeCells excluded cells
	 * @return The number of empty cells considered for the union
	 */
    private int getUnion(BitSet candidates, List<Cell> cells, Collection<Cell> excludeCells) {
    	candidates.clear();
    	int counter = 0;
    	for (Cell cell:cells) {
    		if (cell.isEmpty() && (excludeCells==null || !excludeCells.contains(cell))) {
    			counter++;
    			candidates.or(cell.getPotentialValues());
    		}
    	}
    	return counter;
    }
    
    /**
     * Returns the removeable potentials
     * @param cells
     * @param candidates
     * @param excludeCells
     * @return
     */
    private Map<Cell,BitSet> getRemovablePotentials(Collection<Cell> cells, BitSet candidates, Cell excludeCell) {
        // Build list of removable potentials
        Map<Cell,BitSet> removablePotentials = new HashMap<Cell,BitSet>();
        for (Cell cell:cells) {
        	if (excludeCell==null || !excludeCell.equals(cell)) {
            	BitSet tmp = (BitSet) cell.getPotentialValues().clone();
            	tmp.and(candidates);
            	if (tmp.cardinality()>0) {
                    removablePotentials.put(cell, tmp);
            	}
        	}
        }
        return removablePotentials;
    }
    
    @Override
	public String getProducerName() {
    	return HintResource.getString(R.string.producer_sue_de_coq);
	}

}